# 16/100 数组-除自身以外数组的乘积
# leetcode第238题: https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/20

from leetcode import test


def productExceptSelf(nums: list[int]) -> list[int]:
    """我的解法，考虑count函数统计数组中0的数量，总共遍历了3遍数组"""
    n = len(nums)
    res = [0] * n
    count = nums.count(0)
    if count >= 2:
        return res

    if count == 1:
        temp = 1
        index = nums.index(0)
        for i in range(n):
            if i == index:
                continue
            temp *= nums[i]
        res[index] = temp
        return res

    temp = 1
    for i in range(n):
        temp *= nums[i]
    for i in range(n):
        res[i] = int(temp / nums[i])
    return res


def productExceptSelf_official(nums: list[int]) -> list[int]:
    """官方的解法，遍历了2遍数组"""
    n = len(nums)
    res = [1] * n
    tmp = 1
    for i in range(1, n):
        tmp = tmp * nums[i - 1]
        res[i] = tmp

    tmp = 1
    for i in range(n - 2, -1, -1):
        tmp = tmp * nums[i + 1]
        res[i] = res[i] * tmp

    return res


if __name__ == '__main__':
    inp = [{"nums": [1, 2, 3, 4]}, {"nums": [-1, 1, 0, -3, 3]}, {"nums": [-1, 0, 0, -3, 3]},
           {"nums": [-1, 1, 2, -3, 1, 3, 8, 9, 5, 2, 6, 3, 11, 3, 2, 3, 8, 9, 3, 2, 7, 6, 3, 7, 3, 4, 3, 7, 8, 6, 5, 2,
                     6, 9, 8, 7, 2, 4]}, ]
    out = [[24, 12, 8, 6], [0, 0, 9, 0, 0], [0, 0, 0, 0, 0],
           [-51500160298935071539200, 51500160298935071539200, 25750080149467535769600, -17166720099645023846400,
            51500160298935071539200, 17166720099645023846400, 6437520037366883942400, 5722240033215007948800,
            10300032059787014307840, 25750080149467535769600, 8583360049822511923200, 17166720099645023846400,
            4681832754448642867200, 17166720099645023846400, 25750080149467535769600, 17166720099645023846400,
            6437520037366883942400, 5722240033215007948800, 17166720099645023846400, 25750080149467535769600,
            7357165756990724505600, 8583360049822511923200, 17166720099645023846400, 7357165756990724505600,
            17166720099645023846400, 12875040074733767884800, 17166720099645023846400, 7357165756990724505600,
            6437520037366883942400, 8583360049822511923200, 10300032059787014307840, 25750080149467535769600,
            8583360049822511923200, 5722240033215007948800, 6437520037366883942400, 7357165756990724505600,
            25750080149467535769600, 12875040074733767884800]]

    test.test_function(productExceptSelf, inp, out, times=1000)
    test.test_function(productExceptSelf_official, inp, out, times=1000)
